The present invention relates to a telecommunication network comprising nodes interconnected by paths or links and including a searching arrangement for finding the path of least cost, which arrangement performs an adaptive and decentralized search while cognizance of the overall state of the network is available in each of the nodes.
In a telecommunication network such a searching arrangement is used for finding the best path between two nodes, a node in this case being a channel switch which can be a transmitter and/or a receiver.
The invention likewise relates in a more general way to an adaptive and decentralized searching arrangement for finding the best path in a network that comprises nodes interconnected by links while cognizance of the overall state of the network is available in each of the nodes.
Such a search has been made for a long time in the scope of optimization of systems, specially transport systems.
A communication routing method for a self-switching network is known from document EP-A-0 276 754. In this arrangement an algorithm known as "Dijkstra's" algorithm is used. It is about defining a shortest path routing tree: such a tree has its root at the starting node under consideration, its branches are paths of the network and its forks correspond to nodes of the network which are encountered via the paths, and it shows the best paths between this starting node and each of the other nodes of the network. Since it shows the best paths, it is only valid at a given moment as a function of the loads of the various paths at that moment. Dijkstra's algorithm is an iterative algorithm according to which, for each iteration, a list of nodes is updated which are likely to form part of a shorter path starting from the given node called "root node". A detailed embodiment for this algorithm will be described hereinafter.
Variants of Dijkstra's algorithm are related to modifying the order in which veins of an artery leaving a given node are scanned and also to the number of scannings of these branches. For a proper synthesis with the prior art the document "Description et comparaison des algorithmes de calcul de l'arbre des plus courtes routes" by G. SCHEYS, Technical Note, Philips Research Lab., Brussels, May 1991, may be referred to.